package com.objcat.playground.leetcode;

/**
 * description: Solution22 <br>
 * date: 2022/3/15 12:30 PM <br>
 * author: objcat <br>
 * version: 1.0 <br>
 */
public class Solution24 {

    /**
     * description: 快慢指针法 <br>
     * version: 1.0 <br>
     * date: 2022/3/17 2:25 PM <br>
     * author: objcat <br>
     * @param head 节点头
     * @return boolean 是否闭环
     * 执行用时：0 ms, 在所有 Java 提交中击败了 100 % 的用户
     * 内存消耗：42.3 MB, 在所有 Java 提交中击败了 42.79% 的用户
     */ 
    public boolean hasCycle(ListNode head) {
        // 判断边界
        if (head == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            // 慢指针每次走一步
            slow = slow.next;
            // 快指针每次走一步
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }


    public static void main(String[] args) throws InterruptedException {


        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
//        node4.next = node1;

//        System.out.println(node1);
        long start = System.currentTimeMillis();
        Solution24 solution22 = new Solution24();
        System.out.println(solution22.hasCycle(node1));
        long end = System.currentTimeMillis();
        System.out.println((end - start) / 1000.0);
    }
}
